#include"ggraph.h"

void create (MatGraph **pp_mg, double g[][MAX], int v_num, int e_num)
{
	int i, j;
	*pp_mg = (MatGraph *)malloc(sizeof(MatGraph));
	(*pp_mg)->v_num = 0;
	(*pp_mg)->e_num = 0;

	for (i = 0; i < MAX; ++i)
		for (j = 0; j < MAX; ++j)
				(*pp_mg)->edges[i][j] = g[i][j];
	(*pp_mg)->v_num = v_num;
	(*pp_mg)->e_num = e_num;
}

void print (MatGraph *p_mg)
{
	int i, j;
	
	printf("    %4d%4d%4d%4d%4d%4d%4d\n", 0, 1, 2, 3, 4, 5, 6);
	for (i = 0; i < p_mg->v_num; ++i) {
		printf("  %d:", i);
		for (j = 0; j < p_mg->v_num; ++j)
			if (p_mg->edges[i][j] == INF)
				printf("  <>");
			else
				printf("%4.0f", p_mg->edges[i][j]);
		printf("\n");
	}
}

void destroy (MatGraph *p_mg)
{
	free(p_mg);
}

void make_set (UFSTree *t, int n)
{
	int i;
	for (i = 0; i < n; ++i) {
		t[i].rank = 0;
		t[i].parent = i;
	}
}

int find_set (UFSTree *t, int x)
{
	if (t[x].parent == x)
		return x;
	return (find_set(t, t[x].parent));
}

void union_set (UFSTree *t, int x, int y)
{
	x = find_set(t, x);
	y = find_set(t, y);

	if (t[x].rank > t[y].rank) {
		t[y].parent = x;
	} else {
		t[x].parent = y;
		if (t[x].rank == t[y].rank)
			t[y].rank++;
	}
}

void kruskal (MatGraph *p_mg)
{
	int i, j, e_count, u, v, cmpnt1, cmpnt2;
	UFSTree conn_cmpnts[MAX];
	Edge edges[MAX * (MAX-1)];

	e_count = 0;
	for (i = 0; i < MAX; ++i)
		for (j = 0; j < MAX; ++j)
			if (p_mg->edges[i][j] != 0 && p_mg->edges[i][j] != INF) {
				edges[e_count].u = i;
				edges[e_count].v = j;
				edges[e_count].weight = p_mg->edges[i][j];
				e_count++;
			}

	make_set(conn_cmpnts, MAX);

	insert_sort(edges, e_count);

	for (i = e_count = 0; e_count < MAX - 1; ++i) {
		u = edges[i].u;
		v = edges[i].v;
		cmpnt1 = find_set(conn_cmpnts, u);
		cmpnt2 = find_set(conn_cmpnts, v);
		
		if (cmpnt1 != cmpnt2) {
			printf("the weight of a minimal edge(%d, %d): %f\n",
					u, v, edges[i].weight);
			union_set(conn_cmpnts, cmpnt1, cmpnt2);
			e_count++;
		}
	}
}

void insert_sort (Edge *edges, int n)
{
	int i, j;
	Edge tmp;
	
	for (i = 1; i < n; ++i)
		if (edges[i].weight < edges[i-1].weight) {
			for (tmp = edges[i], j = i-1;
				j >= 0 && tmp.weight < edges[j].weight;
				 --j)
				edges[j+1] = edges[j];
			edges[j+1] = tmp;
		}
}

void dijkstra (MatGraph *p_mg, int v)
{
	int i, j, u;
	int  path[MAX];
	double mid_dis;
	double dist[MAX];
	int S[MAX];

	for (i = 0; i < p_mg->v_num; ++i) {
		S[i] = 0;
		dist[i] = p_mg->edges[v][i];
		if (dist[i] < INF)
			path[i] = v;
		else 
			path[i]  -1;
	}
	
	S[v] = 1;
	for (i = 0; i < p_mg->v_num - 1; ++i) {
		mid_dis = INF;

		for (j = 0; j < p_mg->v_num; ++j)
			if (S[j] == 0 && dist[j] < mid_dis) {
				u = j; mid_dis = dist[j];
			}
		S[u] = 1;

		for (j = 0; j < p_mg->v_num; ++j)
			if (S[j] == 0 && dist[u] + p_mg->edges[u][j] < dist[j]) {
				dist[j] = dist[u] + p_mg->edges[u][j];
				path[j] = u;
			}
	}

	print_sp(S, dist, path, v);
}

void print_sp (int *s, double *dist, int *path, int v)
{
	int i;
	for (i = 0; i < MAX; ++i)
		if (s[i] == -1) {
			printf("the vertex %d has not path from %d to it\n", 
					i, v);
		} else {
			printf("the shortest path from source point %d to vertex %d is", v, i);
			print_core(i, path, v);
			printf(", path long %2.0f\n", dist[i]);
		}
}

void print_core (int i, int *path, int v)
{
	if (i == v) {
		printf(" %d", v);
		return ;
	}

	print_core(path[i], path, v);
	printf(" %d", i);
}
